{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #组合总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combinationSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个<strong>无重复元素</strong>的正整数数组&nbsp;<code>candidates</code>&nbsp;和一个正整数&nbsp;<code>target</code>&nbsp;，找出&nbsp;<code>candidates</code>&nbsp;中所有可以使数字和为目标数&nbsp;<code>target</code>&nbsp;的唯一组合。</p>\n",
    "\n",
    "<p><code>candidates</code>&nbsp;中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。&nbsp;</p>\n",
    "\n",
    "<p>对于给定的输入，保证和为&nbsp;<code>target</code> 的唯一组合数少于 <code>150</code> 个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = [2,3,6,7], target = 7\n",
    "<strong>输出: </strong>[[7],[2,2,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = [2,3,5], target = 8\n",
    "<strong>输出: </strong>[[2,2,2,2],[2,3,3],[3,5]]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = [2], target = 1\n",
    "<strong>输出: </strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = [1], target = 1\n",
    "<strong>输出: </strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = [1], target = 2\n",
    "<strong>输出: </strong>[[1,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= candidates.length &lt;= 30</code></li>\n",
    "\t<li><code>1 &lt;= candidates[i] &lt;= 200</code></li>\n",
    "\t<li><code>candidate</code> 中的每个元素都是独一无二的。</li>\n",
    "\t<li><code>1 &lt;= target &lt;= 500</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 39&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/combination-sum/\">https://leetcode-cn.com/problems/combination-sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Ygoe9J](https://leetcode.cn/problems/Ygoe9J/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Ygoe9J](https://leetcode.cn/problems/Ygoe9J/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6,7]\\n7', '[2,3,5]\\n8', '[2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0 for i in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # @cache\n",
    "        # def dfs(target):\n",
    "        #     if not nums or target<0: return 0\n",
    "        #     mem = set()\n",
    "        #     res = 0\n",
    "        #     for v in nums:\n",
    "        #         if v in mem: continue\n",
    "        #         if v==target: \n",
    "        #             res+=1\n",
    "        #             continue\n",
    "        #         res += dfs(target-v)\n",
    "        #         mem.add(v)\n",
    "        #     return res\n",
    "        # return dfs(target)\n",
    "\n",
    "        nums.sort()\n",
    "        dp = [0]*(target+1)\n",
    "        for i in range(target+1):\n",
    "            if i in nums:\n",
    "                dp[i]=1\n",
    "        for i in range(target+1):\n",
    "            for v in nums:\n",
    "                if v>i: break\n",
    "                dp[i] += dp[i-v]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1 + abs(min(nums))) # 包含负数的情况下 + abs(min(nums)), 防止越界\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1): # 为什么先遍历nums, 结果是错误的?\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target] # 包含负数的情况不能返回dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[1]+[0]*(target)\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i>=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "                    #print(dp)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for j in range(1, target + 1):\n",
    "            for i in range(0, len(nums)):\n",
    "                if j >= nums[i]:\n",
    "                    dp[j] += dp[j - nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(0, target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if (j - nums[i] >= 0):\n",
    "                    dp[j] = dp[j] + dp[j - nums[i]]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1] + [0] * target\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0 for _ in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if i>=j:\n",
    "                   dp[i]=dp[i]+dp[i-j]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + abs(min(nums)) + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1): # 为什么先遍历nums, 结果是错误的?\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i-num >= 0:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for j in range(0, target + 1):\n",
    "            for i in range(0, len(nums)):\n",
    "                if j >= nums[i]:\n",
    "                    dp[j] += dp[j - nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "    dp = [1] + [0 for i in range(target)]\n",
    "\n",
    "    for i in range(1, target + 1):\n",
    "      for num in nums:\n",
    "        if i - num >= 0: dp[i] += dp[i - num]\n",
    "    \n",
    "    return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for j in range(target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if j-nums[i]>=0:\n",
    "                    dp[j] += dp[j-nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1]+[0]*target\n",
    "        for i in range(target):\n",
    "            if dp[i] == 0: continue\n",
    "            for n in nums:\n",
    "                if i+n <= target: dp[i+n] += dp[i]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        f = [0] * (target+1)\n",
    "        f[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    f[i] += f[i-num]\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i>= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        #dp[i][j]代表 0-i个数组成j的个数\n",
    "        dp=[0 for _ in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for n in nums:\n",
    "                if i>=n:\n",
    "                  dp[i]+=dp[i-n]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# res = 0\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        dp = [0]*(target+2)\n",
    "\n",
    "        use = []\n",
    "        for tmp in nums:\n",
    "            if tmp <= target:\n",
    "                use.append(tmp)\n",
    "        for tmp in use:\n",
    "            dp[tmp+1]=1\n",
    "\n",
    "        for i in range(target+2):\n",
    "            for tmp in use:\n",
    "                if i-tmp>0 and dp[i-tmp]>0:\n",
    "                    dp[i]=dp[i-tmp]+dp[i]\n",
    "        \n",
    "        return dp[target+1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num>=0:dp[i]+=dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        if target == 0:\n",
    "            return 1\n",
    "        if min(nums) > target:\n",
    "            return 0\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1] + [0] * target\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i - num]\n",
    "        \n",
    "        return dp[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        f = [0] * (target + 1)\n",
    "        f[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    f[i] += f[i - num]\n",
    "        return f[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        nums.sort()\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "                \n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # 完全背包，排列\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if j < nums[i]:\n",
    "                    continue\n",
    "                dp[j] += dp[j-nums[i]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for j in range(1,target+1):\n",
    "            for i in range(n):\n",
    "                if nums[i]<=j:dp[j]+=dp[j-nums[i]]\n",
    "        #组合问题 1、2和2、1相同，先遍历物品再遍历容量，这样出现了3，1，2不会再出现3，2，1\n",
    "        #排列问题 1、2和2、1不同，先遍历容量再遍历物品\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            dp[i] += sum(dp[i-num] for num in nums if i-num>=0)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        dp[0] = 1\n",
    "\n",
    "        for t in range(1, target+1):\n",
    "            # 由于nums元素各不相同\n",
    "            # 在newTarget基础上增加一个num，组合方式一定各不相同\n",
    "            for num in nums:\n",
    "                if t - num < 0:\n",
    "                    break\n",
    "                else:\n",
    "                    newTarget = t - num\n",
    "                    dp[t] += dp[newTarget]\n",
    "        \n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range (1,target+1):\n",
    "            for k in nums:\n",
    "                if k<=i:\n",
    "                    dp[i]=dp[i]+dp[i-k]\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        # f(i)表示走到第i个台阶需要走多少步\n",
    "        # 范围 target + 1\n",
    "        # dp = []*(target+1)\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for j in range(len(nums)):\n",
    "                if (i-nums[j])>= 0 :\n",
    "                    dp[i] += dp[i-nums[j]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        #容量为target的完全背包\n",
    "        #dp[j] += dp[j-nums[i]]\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] =1\n",
    "        for j in range(1,target+1):#\n",
    "            for i in nums:\n",
    "                if j-i >= 0:\n",
    "                    dp[j] +=dp[j-i]\n",
    "                          \n",
    "        return dp[target]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, target + 1):\n",
    "            for n in nums:\n",
    "                if i >= n:\n",
    "                    dp[i] += dp[i - n]\n",
    "                    \n",
    "        return dp[target]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + abs(min(nums)) + 1) # 包含负数的情况\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1): # 为什么先遍历nums, 结果是错误的?\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target] # 包含负数的情况不能返回dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if i-j>=0:\n",
    "                    dp[i]+=dp[i-j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for j in range(n):\n",
    "                if(i>=nums[j]):\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i] += dp[i-nums[j]]\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(target+1)\n",
    "        for j in range(n):\n",
    "            if nums[j]<=target:\n",
    "                dp[nums[j]] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for j in range(n):\n",
    "                if i>=nums[j]:\n",
    "                    dp[i] += dp[i-nums[j]]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for c in nums:\n",
    "                if c <= i:\n",
    "                    dp[i] += dp[i-c]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num>=0:dp[i]+=dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # 如果有负数我就不能dp了啊 麻了 看了一眼有负数的解决方案是直接截断\n",
    "        dp = [0 for i in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] = dp[i] + dp[i-num]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        mem = {}\n",
    "\n",
    "        def backtrack(target):\n",
    "            if target in mem:\n",
    "                return mem[target]\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if nums[i] < target:\n",
    "                    ans += backtrack(target - nums[i])\n",
    "                elif nums[i] == target:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    break\n",
    "            mem[target] = ans\n",
    "            return ans\n",
    "\n",
    "        return backtrack(target)\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0 for i in range(target+1)]\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [1] + [0] * target\n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i - num]\n",
    "        \n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num>=0:dp[i]+=dp[i-num]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # 状态转移方程 dp[i] += dp[i-nums[j]]\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if j <= i:\n",
    "                    dp[i] += dp[i-j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#组合总和 Ⅳ,输入：nums = [1,2,3], target = 4,输出：7,所有可能的组合为：(1, 1, 1, 1)\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num<=i:dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        num=len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            res=0\n",
    "            if s==target:\n",
    "                res+=1\n",
    "                \n",
    "            for i in range(num):\n",
    "                if nums[i]+s<=target:\n",
    "                    res+=dfs(s+nums[i])\n",
    "            return res\n",
    "        res=dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        # dp[i]:nums构成综合为i的排列个树\n",
    "        dp  = [0]*(target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1,1):\n",
    "            for j in range(0,i,1):\n",
    "                if i-j in nums:\n",
    "                    dp[i] +=dp[j]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i == num:\n",
    "                    dp[i] += 1\n",
    "                dp[i] += dp[max(0, i-num)]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i == num:\n",
    "                    dp[i] += 1\n",
    "                dp[i] += dp[max(0, i-num)]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if num<=i:dp[i]+=dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i == target:\n",
    "             return 1\n",
    "          res = 0\n",
    "          for num in nums:\n",
    "             if num + i <= target:\n",
    "                res += dfs(i + num)\n",
    "          return res\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                dp[i] += (i >= num and dp[i - num])\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 动态规划\n",
    "        # dp = [0] * (target + 1)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(1, target + 1):\n",
    "        #     for num in nums:\n",
    "        #         dp[i] = dp[i] + (num <= i and dp[i - num])\n",
    "\n",
    "        # return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                dp[i] += (i >= num and dp[i - num])\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 动态规划\n",
    "        # dp = [0] * (target + 1)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(1, target + 1):\n",
    "        #     for num in nums:\n",
    "        #         dp[i] = dp[i] + (num <= i and dp[i - num])\n",
    "\n",
    "        # return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        method = 'mine2'\n",
    "        if method == 'mine':\n",
    "            def dfs(comb, target):\n",
    "                if target < 0: return\n",
    "                if target == 0:\n",
    "                    res.append(comb[:])\n",
    "                for i in range(n):\n",
    "                    dfs(comb + [nums[i]], target - nums[i])\n",
    "\n",
    "            n = len(nums)\n",
    "            res = []\n",
    "            dfs([], target)\n",
    "            return len(res)\n",
    "\n",
    "        if method == 'mine2':\n",
    "            n = len(nums)\n",
    "            dp = [0] * ( target + 1 )\n",
    "            dp[0] = 1\n",
    "            for i in range(1, target + 1):\n",
    "                for j in range(n):\n",
    "                    if i >= nums[j]:\n",
    "                        dp[i] += dp[i - nums[j]]\n",
    "             \n",
    "\n",
    "            return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        #容量为target的完全背包\n",
    "        #dp[j] += dp[j-nums[i]]\n",
    "        dp = [0]*(target+1)\n",
    "        dp[0] =1\n",
    "        for j in range(1,target+1):#\n",
    "            for i in nums:\n",
    "                if j-i >= 0:\n",
    "                    dp[j] +=dp[j-i]\n",
    "                          \n",
    "        return dp[target]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(count=0):\n",
    "            if count>target:\n",
    "                return 0\n",
    "            ans=0\n",
    "            if count==target:\n",
    "                ans+=1\n",
    "            for j in nums:\n",
    "                if count+j<=target:\n",
    "                  ans+=dfs(count+j)\n",
    "            return ans\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        num=len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            res=0\n",
    "            if s==target:\n",
    "                res+=1\n",
    "                \n",
    "            for i in range(num):\n",
    "                if nums[i]+s<=target:\n",
    "                    res+=dfs(s+nums[i])\n",
    "            return res\n",
    "        res=dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i < num:\n",
    "                    continue\n",
    "                dp[i] += dp[max(0, i-num)]\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        #nums.sort()\n",
    "        n=len(nums)\n",
    "        #path=[]\n",
    "        \n",
    "        # def dfs(i,c):\n",
    "            \n",
    "            \n",
    "\n",
    "        #     if i<0:\n",
    "        #         return 1 if c==0 else 0\n",
    "        #     # if c<nums[0]:\n",
    "        #     #     return 0\n",
    "            \n",
    "\n",
    "        #     if c<nums[i]:\n",
    "        #         return dfs(i-1,c)\n",
    "\n",
    "        #     return dfs(i-1,c)+dfs(i,c-nums[i])\n",
    "\n",
    "\n",
    "        # return dfs(n-1,target)\n",
    "        #path=[]\n",
    "        @cache\n",
    "        def dfs(c):\n",
    "\n",
    "            if c ==0:\n",
    "                return 1 \n",
    "           \n",
    "        \n",
    "\n",
    "            res=0\n",
    "            for j in range(n):\n",
    "                if c>=nums[j]:\n",
    "                    res+=dfs(c-nums[j])\n",
    "                   \n",
    "            return res\n",
    "\n",
    "        return  dfs(target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dp(x):\n",
    "            ans = 0\n",
    "            for number in nums:\n",
    "                if number == x:\n",
    "                    ans += 1\n",
    "                elif number < x:\n",
    "                    ans += dp(x - number)\n",
    "            return ans\n",
    "\n",
    "        return dp(target)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(tmp=0):\n",
    "            ans = 0\n",
    "            if tmp == target:\n",
    "                ans += 1\n",
    "            for each in nums:\n",
    "                if each + tmp<= target:\n",
    "                    ans += dfs(tmp+each)\n",
    "            return ans\n",
    "        return dfs()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            next_nums = []\n",
    "            for v in nums:\n",
    "                if v<=target: next_nums.append(v)\n",
    "            if not next_nums: return 0\n",
    "            mem = set()\n",
    "            res = 0\n",
    "            for v in next_nums:\n",
    "                if v in mem: continue\n",
    "                if v==target: \n",
    "                    res+=1\n",
    "                    continue\n",
    "                res += dfs(target-v)\n",
    "                mem.add(v)\n",
    "            return res\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(tmp=0):\n",
    "            ans = 0\n",
    "            if tmp == target:\n",
    "                ans += 1\n",
    "            for each in nums:\n",
    "                if each + tmp<= target:\n",
    "                    ans += dfs(tmp+each)\n",
    "            return ans\n",
    "        return dfs()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @functools.lru_cache(maxsize=None)\n",
    "        def sol(t) :\n",
    "            if t == 0 : return 1\n",
    "            return sum([sol(t-n) for n in nums if t-n >= 0])\n",
    "        return sol(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                res += dp(i-num)\n",
    "            return res\n",
    "        return dp(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            if not nums or target<0: return 0\n",
    "            mem = set()\n",
    "            res = 0\n",
    "            for v in nums:\n",
    "                if v in mem: continue\n",
    "                if v==target: \n",
    "                    res+=1\n",
    "                    continue\n",
    "                res += dfs(target-v)\n",
    "                mem.add(v)\n",
    "            return res\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(total):\n",
    "            if total == 0:\n",
    "                return 1\n",
    "            elif total < 0:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "            for i in range(len(nums)):\n",
    "                ans += dp(total - nums[i])\n",
    "            return ans\n",
    "        return dp(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def solve(s):\n",
    "            if s == target:\n",
    "                return 1\n",
    "            if s > target:\n",
    "                return 0\n",
    "            c = 0\n",
    "            for n in nums:\n",
    "                c += solve(s + n)\n",
    "            return c\n",
    "        return solve(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(target):\n",
    "            if target==0:return 1\n",
    "            if target<0:return 0\n",
    "            return sum(dfs(target-i) for i in nums)\n",
    "        return dfs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        res=[]\n",
    "        self.dfs(candidates, 0, target, ans,res)\n",
    "        return ans\n",
    "    def dfs(self, candidates, idx, target, ans, res):\n",
    "        if target==0:\n",
    "            ans.append(res[:])\n",
    "            return \n",
    "        if idx==len(candidates):\n",
    "            return\n",
    "        \n",
    "        self.dfs(candidates, idx+1, target, ans, res)\n",
    "        if target>=candidates[idx]:\n",
    "            res.append(candidates[idx])\n",
    "            self.dfs(candidates, idx, target-candidates[idx], ans, res)\n",
    "            res.pop()\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = self.func1(candidates,target,[],[])\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def func1(self,candidates,target,arr1,arr2):\n",
    "        if target<0:\n",
    "            return arr2\n",
    "        if target==0:\n",
    "            arr2.append(arr1)\n",
    "        for i in range(len(candidates)):\n",
    "            arr1.append(candidates[i])\n",
    "            self.func1(candidates[i:],target-candidates[i],arr1[:],arr2)\n",
    "            arr1.pop()\n",
    "        return arr2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # candidates.sort()\n",
    "        self.candidates = candidates\n",
    "        ans = self.helper(0, target)\n",
    "        return ans\n",
    "\n",
    "    # @lru_cache(None)\n",
    "    def helper(self, hidx, target):\n",
    "        \"\"\" \n",
    "        candidate 从 hidx开始的元素是否可以重复使用组成 target\n",
    "        \"\"\"\n",
    "        if target == 0: return [[]]\n",
    "        if hidx == len(self.candidates): return []\n",
    "\n",
    "        ans = []\n",
    "        val = self.candidates[hidx]\n",
    "        for t in range(target//val+1):\n",
    "            res = self.helper(hidx+1, target-val*t)\n",
    "            tmp = [ [val]*t + i for i in res ]\n",
    "            ans.extend(tmp)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        arr = []\n",
    "        def tracrBack(i, path, target):\n",
    "            if target<0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                arr.append(path[:])\n",
    "                return\n",
    "            for idx in range(i, len(candidates)):\n",
    "                path.append(candidates[idx])\n",
    "                tracrBack(idx, path, target-candidates[idx])\n",
    "                path.pop()\n",
    "        tracrBack(0, [], target)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    经典题解：https://leetcode.cn/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/\n",
    "    \"\"\"\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def compute(nums, target, path):\n",
    "            if target < 0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                nonlocal res\n",
    "                ans = [int(item) for item in path.split(\"->\") if item != '']\n",
    "                ans.sort()\n",
    "                if ans not in res:\n",
    "                    res.append(ans)\n",
    "                return\n",
    "\n",
    "            if len(nums) <= 0:\n",
    "                return\n",
    "            for item in nums:\n",
    "                compute(nums, target-item, path+\"->\"+str(item))\n",
    "        compute(candidates, target, \"\")\n",
    "        return res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        {'candidates': [2,3,6,7], 'target': 7},\n",
    "        {'candidates': [2,3,5], 'target': 8},\n",
    "        {'candidates': [2], 'target': 1},\n",
    "    ]:\n",
    "        ret = s.combinationSum(testcase['candidates'], testcase['target'])\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates=sorted(candidates)\n",
    "        def backtrack(res,temp,candidates,cur,idx):\n",
    "            if cur<0:\n",
    "                return\n",
    "            elif cur==0:\n",
    "                res.append(copy.deepcopy(temp))\n",
    "            else:\n",
    "                for i in range(idx,len(candidates)):\n",
    "                    temp.append(candidates[i])\n",
    "                    backtrack(res,temp,candidates,cur-candidates[i],i)\n",
    "                    temp.pop()\n",
    "        res = []\n",
    "        backtrack(res,[],candidates,target,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n=len(candidates)\n",
    "        ans=[]\n",
    "        def dfs(idx,cnt,path):\n",
    "            if cnt==target:\n",
    "                ans.append(path[:])\n",
    "                return \n",
    "            if idx>n-1 or cnt>target:\n",
    "                return \n",
    "            dp=[]\n",
    "            for i in range(idx,n):\n",
    "                if candidates[i] not in dp and candidates[i]+cnt<=target:\n",
    "                    dp.append(candidates[i])\n",
    "                    path.append(candidates[i])\n",
    "                    dfs(i,cnt+candidates[i],path)\n",
    "                    path.pop()\n",
    "                    dp.pop()\n",
    "        dfs(0,0,[])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \n",
    "        cur = []\n",
    "        res = []\n",
    "        def back_trace(pos):\n",
    "            cur_sum = sum(cur)\n",
    "            if cur_sum == target:\n",
    "                res.append(cur[:])\n",
    "                return\n",
    "            elif cur_sum > target:\n",
    "                return\n",
    "            \n",
    "            for i in range(pos, len(candidates)):\n",
    "                cur.append(candidates[i])\n",
    "                back_trace(i)\n",
    "                cur.pop()\n",
    "        \n",
    "        back_trace(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 回溯，无重复元素，根据剩余值凑成目标\n",
    "        ans = []\n",
    "        path = []\n",
    "        candidates.sort() # 预先排序，\n",
    "        # 收集逻辑为target == 0\n",
    "\n",
    "        def backtracking(index,path,target):\n",
    "            if index >= len(candidates) or target < 0:\n",
    "                return \n",
    "            if target == 0: # 收集条件\n",
    "                ans.append(path[:])\n",
    "                return    \n",
    "            for i in range(index,len(candidates)):  # 注意可以重复收集          \n",
    "                 # 做选择\n",
    "                backtracking(i,path+[candidates[i]],target-candidates[i])\n",
    "                # 取消选择\n",
    "         \n",
    "        backtracking(0,[],target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(k,n,path,sum,target,res):\n",
    "            if sum>=target:\n",
    "                if sum==target:\n",
    "                    res.append(path)\n",
    "                return res\n",
    "            for i in range(k,n):\n",
    "                res = dfs(i,n,path+[candidates[i]],sum+candidates[i],target,res)\n",
    "            return res\n",
    "        return dfs(0,len(candidates),[],0,target,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "\n",
    "        def dfs(index: int, rest: int):\n",
    "            if rest < 0:\n",
    "                return\n",
    "            if rest == 0:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                path.append(candidates[i])\n",
    "                dfs(i, rest - candidates[i])\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "        self.back(res, [], 0, candidates, target)\n",
    "        return res\n",
    "    \n",
    "    def back(self, res, tmp, k, nums, K):\n",
    "        if K == 0:\n",
    "            res.append(tmp)\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] <= K:\n",
    "                self.back(res, tmp+[nums[i]], i, nums, K-nums[i])\n",
    "            else:\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        candidates.sort()\n",
    "\n",
    "        def backtracking(index,path,target):\n",
    "            if index>=len(candidates) or target < 0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(index,len(candidates)):\n",
    "                path.append(candidates[i])\n",
    "                backtracking(i,path,target-candidates[i])\n",
    "                path.pop()\n",
    "        backtracking(0,[],target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            n = len(candidates)\n",
    "            def dfs(begin, comb, target):\n",
    "                if target < 0:\n",
    "                    return\n",
    "                if target == 0:\n",
    "                    res.append(comb)\n",
    "                    return\n",
    "                for i in range(begin, n):\n",
    "                    dfs(i, comb + [candidates[i]], target - candidates[i])\n",
    "            res = []        \n",
    "            dfs(0, [], target)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "\n",
    "        ans = []\n",
    "        def backtrack(path, idx):\n",
    "            if sum(path)==target:\n",
    "                ans.append(path+[])\n",
    "                return\n",
    "            if sum(path)>target:\n",
    "                return\n",
    "            \n",
    "            for i in range(idx, n):\n",
    "                path.append(candidates[i])\n",
    "                backtrack(path, i)\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack([], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "\n",
    "        def backtrace(cur_list, idx):\n",
    "            if sum(cur_list)==target:\n",
    "                res.append(cur_list[:])\n",
    "            elif sum(cur_list) > target:\n",
    "                return\n",
    "            for i in range(idx, len(candidates)):\n",
    "                cur_list.append(candidates[i])\n",
    "                backtrace(cur_list, i)\n",
    "                cur_list.pop()\n",
    "        backtrace([],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pathSum = 0\n",
    "        self.path = []\n",
    "        self.res = []\n",
    "\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.backtrack(candidates, target, 0)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, candidates, target, start):\n",
    "        if self.pathSum == target:\n",
    "            self.res.append(self.path[:])\n",
    "            return\n",
    "        if self.pathSum > target:\n",
    "            return\n",
    "        for i in range(start, len(candidates)):\n",
    "            self.pathSum += candidates[i]\n",
    "            self.path.append(candidates[i])\n",
    "            self.backtrack(candidates, target, i)\n",
    "            self.pathSum -= candidates[i]\n",
    "            self.path.pop()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        paths = []\n",
    "    \n",
    "        def dfs(candidates, target, idx, path):\n",
    "            \n",
    "            if target == 0:\n",
    "                paths.append(path)\n",
    "            \n",
    "            for i, candidate in enumerate(candidates):\n",
    "                if i < idx:\n",
    "                    continue\n",
    "                    \n",
    "                if candidate <= target:\n",
    "                    dfs(candidates, target-candidate, i, path + [candidate])\n",
    "        \n",
    "\n",
    "        dfs(candidates, target, 0, [])\n",
    "        return paths\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(path, startIdx):\n",
    "            nonlocal res\n",
    "            if sum(path) > target:\n",
    "                return \n",
    "            if sum(path) == target:\n",
    "                return res.append(path[:])\n",
    "            for i in range(startIdx, len(candidates)):\n",
    "                path.append(candidates[i])\n",
    "                dfs(path, i)\n",
    "                path.pop()\n",
    "        res = []\n",
    "        dfs([], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        candidates.sort()\n",
    "        path = []\n",
    "        def dfs(s,cur):\n",
    "            if cur == target:\n",
    "                self.res.append(path.copy())\n",
    "                return \n",
    "\n",
    "            for i in range(s,len(candidates)):\n",
    "                cur += candidates[i]\n",
    "                if cur <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    dfs(i,cur)\n",
    "                    path.pop()\n",
    "                    cur -= candidates[i]\n",
    "                else:\n",
    "                    return \n",
    "        dfs(0,0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        for ind in range(len(candidates)):\r\n",
    "            v = candidates[ind]\r\n",
    "            if v > target:\r\n",
    "                continue\r\n",
    "            elif v == target:\r\n",
    "                res.append([v])\r\n",
    "            elif v < target:\r\n",
    "                tt = self.combinationSum(candidates[ind:], target-v)\r\n",
    "                if tt:\r\n",
    "                    res += [[v]+c_tt for c_tt in tt]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 对candidates进行排序\n",
    "        candidates.sort()\n",
    "        path = []\n",
    "        res = []\n",
    "        def backwards(start, sum, candidates):\n",
    "            # sum == target,将path添加到res中\n",
    "            if sum == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            # 剪枝\n",
    "            for i in range(start, len(candidates)):\n",
    "                sum += candidates[i]\n",
    "                # 剪枝\n",
    "                # 判断sum是否大于target，因为candidates是从小到大的，\n",
    "                # 若sum大于target，则不遍历序号i之后的值；\n",
    "                # 若sum小于target，将candidates[i]添加到path中，然后进行回溯\n",
    "                if sum <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    backwards(i, sum, candidates)\n",
    "                    path.pop()\n",
    "                    sum -= candidates[i]\n",
    "                else:\n",
    "                    return\n",
    "        backwards(0, 0, candidates)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "        self.ans = []\n",
    "        def recur(index, cur):\n",
    "            cur_sum = sum(cur)\n",
    "            if cur_sum > target:\n",
    "                return\n",
    "            if cur_sum == target:\n",
    "                self.ans.append(cur[:])\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                cur.append(candidates[i])\n",
    "                recur(i, cur)\n",
    "                cur.pop()\n",
    "            return\n",
    "        recur(0, [])\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/bao-li-sou-96f79/hui-su-sua-c26da/\n",
    "# 元素无重可复选，组合/子集问题\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = [] # 这里定义track也可以\n",
    "\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # track = []\n",
    "        # self.backtrack(candidates, track, 0, target)\n",
    "        self.backtrack(candidates, 0, target)\n",
    "\n",
    "        return self.res\n",
    "    \n",
    "    # def backtrack(self, candidates, track, start, target):\n",
    "    def backtrack(self, candidates, start, target):\n",
    "        # 终止条件\n",
    "        if sum(self.track) == target:\n",
    "            self.res.append(self.track[:])\n",
    "            return\n",
    "        if sum(self.track) > target:\n",
    "            return\n",
    "        \n",
    "        # 循环每一个选择\n",
    "        for i in range(start, len(candidates)):\n",
    "            # 做选择\n",
    "            self.track.append(candidates[i])\n",
    "            # 递归\n",
    "            # self.backtrack(candidates, track, i, target)\n",
    "            self.backtrack(candidates, i, target)\n",
    "            # 撤回选择\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        #完全背包求组合数，先物品再背包，初始化，求个数\n",
    "        # dp=[0]*(target+1)\n",
    "        # dp[0]=1\n",
    "        # for i in range(len(candidates)):\n",
    "        #     for j in range(candidates[i],target+1):\n",
    "        #         dp[j]=dp[j-candidates[i]]+dp[j]\n",
    "        # return dp[-1]\n",
    "\n",
    "        #回溯求集合\n",
    "        def backtracking(candidates,target,total,startIndex,path,result):\n",
    "            if total==target:\n",
    "                result.append(path[:])\n",
    "                return\n",
    "            for i in range(startIndex,len(candidates)):\n",
    "                if total>target:\n",
    "                    return\n",
    "                total+=candidates[i]\n",
    "                path.append(candidates[i])\n",
    "                backtracking(candidates,target,total,i,path,result)\n",
    "                total-=candidates[i]\n",
    "                path.pop()\n",
    "\n",
    "        result=[]\n",
    "        backtracking(candidates,target,0,0,[],result)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        results = []\n",
    "        path = []\n",
    "        candidates.sort()\n",
    "        self.back_tracking(candidates, target, path, results, 0)\n",
    "        return results\n",
    "\n",
    "    def back_tracking(self, candidates, target, path, results, start_index):\n",
    "        if sum(path) > target:\n",
    "            return\n",
    "        if sum(path) == target:\n",
    "            path = path.copy()\n",
    "            results.append(path)\n",
    "            return\n",
    "        for i in range(start_index, len(candidates)):\n",
    "            if sum(path) > target:\n",
    "                break\n",
    "            path.append(candidates[i])\n",
    "            self.back_tracking(candidates, target, path, results, i)\n",
    "            path.pop()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        temp = []\n",
    "        self.dfs(candidates, res, temp, 0, target)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, candidates, res, reslist, start, n):\n",
    "        if n <= 0:\n",
    "            if n == 0:\n",
    "                temp = copy.deepcopy(reslist)\n",
    "                res.append(temp)\n",
    "            return\n",
    "        for i in range(start, len(candidates)):\n",
    "            reslist.append(candidates[i])\n",
    "            self.dfs(candidates, res, reslist, i, n - candidates[i])\n",
    "            reslist.pop(len(reslist)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        arr = []\n",
    "        candidates.sort()\n",
    "        def traceBack(candidates, path, target):\n",
    "            if target<0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                arr.append(path[:])\n",
    "                return\n",
    "            for i in range(len(candidates)):\n",
    "                if path and candidates[i] < path[-1]: \n",
    "                     continue\n",
    "                path.append(candidates[i])\n",
    "                traceBack(candidates, path, target - candidates[i])\n",
    "                path.pop()\n",
    "        traceBack(candidates, [], target)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.res=[]\n",
    "        now=[]\n",
    "        self.search(candidates, target, now, 0)\n",
    "        return self.res\n",
    "\n",
    "    def search(self, candidates, target, now, index):\n",
    "        if target==0:\n",
    "            self.res.append(copy.deepcopy(now))\n",
    "        if target<0:\n",
    "            return\n",
    "        m=len(candidates)\n",
    "        for i in range(index, m):\n",
    "            now.append(candidates[i])\n",
    "            self.search(candidates, target-candidates[i], now, i)\n",
    "            now.pop()\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        s = len(candidates)\n",
    "        candidates.sort()\n",
    "        def bracket(i,total,track):\n",
    "            if total > target or i == s:\n",
    "                return\n",
    "            if total == target:\n",
    "                result.append(track)\n",
    "                return\n",
    "            bracket(i,total+candidates[i],track+[candidates[i]])\n",
    "            bracket(i+1,total,track)\n",
    "        bracket(0,0,[])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 对candidates进行排序\n",
    "        candidates.sort()\n",
    "        path = []\n",
    "        res = []\n",
    "        def backwards(start, sum, candidates):\n",
    "            # sum == target,将path添加到res中\n",
    "            if sum == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            # 剪枝\n",
    "            for i in range(start, len(candidates)):\n",
    "                sum += candidates[i]\n",
    "                # 剪枝\n",
    "                # 判断sum是否大于target，因为candidates是从小到大的，\n",
    "                # 若sum大于target，则不遍历序号i之后的值；\n",
    "                # 若sum小于target，将candidates[i]添加到path中，然后进行回溯\n",
    "                if sum <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    backwards(i, sum, candidates)\n",
    "                    path.pop()\n",
    "                    sum -= candidates[i]\n",
    "                else:\n",
    "                    return\n",
    "        backwards(0, 0, candidates)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(candidates)\n",
    "        if n == 0:\n",
    "            return ans\n",
    "\n",
    "        path = []\n",
    "        def helper(index, total):\n",
    "            if total == target:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            if total > target:\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                total += candidates[i]\n",
    "                path.append(candidates[i])\n",
    "                helper(i, total)\n",
    "                path.pop()\n",
    "                total -= candidates[i]\n",
    "        helper(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.track = []\n",
    "        self.res = []\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.backtrack(candidates,0,target)\n",
    "        return self.res\n",
    "    def backtrack(self,nums,start,target):\n",
    "        # base case\n",
    "        if sum(self.track)==target:\n",
    "            self.res.append(self.track[:])\n",
    "            return \n",
    "        # base case\n",
    "        # 关键一步 大于目标值的路径没必要继续遍历\n",
    "        if sum(self.track) > target:\n",
    "            return\n",
    "\n",
    "        for i in range(start,len(nums)):\n",
    "            self.track.append(nums[i])\n",
    "            self.backtrack(nums,i,target)\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        arr = []\n",
    "        tt = []\n",
    "        dfs(0,target,arr,candidates,tt)\n",
    "        return tt\n",
    "\n",
    "def dfs(i,target,arr,candidates,tt):\n",
    "    if (target == 0):\n",
    "        tt.append(arr.copy())\n",
    "        return\n",
    "    if(i==len(candidates) and target!=0):\n",
    "        return\n",
    "    if(target<0): return\n",
    "    # 添加当前节点\n",
    "    arr.append(candidates[i])\n",
    "    dfs(i,target-candidates[i],arr,candidates,tt)\n",
    "    arr.pop(-1)\n",
    "    if(target<candidates[i]): return\n",
    "    dfs(i + 1, target, arr, candidates, tt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 回溯，无重复元素，根据剩余值凑成目标\n",
    "        ans = []\n",
    "        path = []\n",
    "        candidates.sort() # 预先排序，\n",
    "        # 收集逻辑为target == 0\n",
    "\n",
    "        def backtracking(index,path,target):\n",
    "            if index >= len(candidates) or target < 0:\n",
    "                return \n",
    "            if target == 0: # 收集条件\n",
    "                ans.append(path[:])\n",
    "                return    \n",
    "            for i in range(index,len(candidates)):  # 注意可以重复收集          \n",
    "                 # 做选择\n",
    "                backtracking(i,path+[candidates[i]],target-candidates[i])\n",
    "                # 取消选择\n",
    "         \n",
    "        backtracking(0,[],target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 回溯，无重复元素，根据剩余值凑成目标\n",
    "        ans = []\n",
    "        path = []\n",
    "        candidates.sort() # 预先排序，\n",
    "        # 收集逻辑为target == 0\n",
    "\n",
    "        def backtracking(index,path,target):\n",
    "            if index >= len(candidates) or target < 0:\n",
    "                return \n",
    "            if target == 0: # 收集条件\n",
    "                ans.append(path[:])\n",
    "                return    \n",
    "            for i in range(index,len(candidates)):  # 注意可以重复收集          \n",
    "                path.append(candidates[i])  # 做选择\n",
    "                backtracking(i,path,target-candidates[i])\n",
    "                path.pop() # 取消选择\n",
    "         \n",
    "        backtracking(0,[],target)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # candidates.sort(reverse=True)\n",
    "        ans = []\n",
    "        tmp = []\n",
    "        Len = len(candidates)\n",
    "        candidates.sort()\n",
    "        def f(i, left):\n",
    "            \n",
    "            if i == Len:\n",
    "                return\n",
    "            n = left // candidates[i]\n",
    "            if n == 0:\n",
    "                return \n",
    "            for k in range(0, n+1):\n",
    "                if candidates[i] * k == left:\n",
    "                    tmp.extend([candidates[i]] * k)\n",
    "                    ans.append(tmp.copy())\n",
    "                    for _ in range(k):\n",
    "                        tmp.pop()\n",
    "                else :\n",
    "                    tmp.extend([candidates[i]] * k)\n",
    "                    f(i+1, left-candidates[i] * k)\n",
    "                    for _ in range(k):\n",
    "                        tmp.pop()\n",
    "\n",
    "        f(0, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "        ans = []\n",
    "        combine = []\n",
    "        \n",
    "        def dfs(target: int, idx: int) -> None:\n",
    "            if idx == n:\n",
    "                return\n",
    "\n",
    "            if target == 0:\n",
    "                ans.append(combine[:])\n",
    "                return\n",
    "            \n",
    "            dfs(target, idx + 1)\n",
    "\n",
    "            if target - candidates[idx] >= 0:\n",
    "                combine.append(candidates[idx])\n",
    "                dfs(target - candidates[idx], idx)\n",
    "                combine.pop()\n",
    "\n",
    "        dfs(target, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "\n",
    "        def dfs(p, s, path):\n",
    "            if s == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            elif s > target:\n",
    "                return \n",
    "            \n",
    "            for i in range(p, n):\n",
    "                path.append(candidates[i])\n",
    "                dfs(i, s + candidates[i], path)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0, 0, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        path =[]\n",
    "        ans = []\n",
    "        candidates.sort()\n",
    "        sums = 0\n",
    "        n = len(candidates)\n",
    "        def dfs(i:int):\n",
    "            nonlocal sums\n",
    "            if sums > target:\n",
    "                return   # 直接退出\n",
    "            if sums == target:\n",
    "                ans.append(path.copy()) \n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                path.append(candidates[j]) \n",
    "                sums+=candidates[j]\n",
    "                dfs(j)\n",
    "                if sums >= target:\n",
    "                    sums -= path.pop()\n",
    "                    #path.pop()\n",
    "                    return \n",
    "\n",
    "                sums -= path.pop()\n",
    "                \n",
    "        dfs(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.trackSum = 0\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        track = []\n",
    "        self.backtrack(candidates,0,track,target)\n",
    "        return self.res\n",
    "    def backtrack(self,candidates: List[int], start:int,track:List[int],target:int) ->None:\n",
    "        if self.trackSum > target:\n",
    "            return\n",
    "        if self.trackSum == target:\n",
    "            self.res.append(track[:])\n",
    "            return\n",
    "        for i in range(start, len(candidates)):\n",
    "            self.trackSum += candidates[i]\n",
    "            track.append(candidates[i])\n",
    "            self.backtrack(candidates, i, track, target)\n",
    "            track.pop()\n",
    "            self.trackSum -= candidates[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(target,idx):\n",
    "            \n",
    "            if idx==len(candidates) or target<0:\n",
    "                return \n",
    "            if target==0:\n",
    "                ans.append(squence[:])\n",
    "                return \n",
    "            dfs(target,idx+1)\n",
    "            squence.append(candidates[idx])\n",
    "            dfs(target-candidates[idx],idx)\n",
    "            squence.pop()\n",
    "        squence=list()\n",
    "        ans=list()\n",
    "        candidates.sort()\n",
    "        dfs(target,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        reslist = []\n",
    "        path = []\n",
    "\n",
    "        def backtracking(startindex, cursum):\n",
    "            if cursum > target:\n",
    "                return\n",
    "            if cursum == target:\n",
    "                reslist.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for i in range(startindex, len(candidates)):\n",
    "                path.append(candidates[i])\n",
    "                cursum += candidates[i]\n",
    "                backtracking(i, cursum)\n",
    "                path.pop()\n",
    "                cursum -= candidates[i]\n",
    "            return\n",
    "        backtracking(0, 0)\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        self.nums = candidates\n",
    "        self.backTrack([], 0, target, 0)\n",
    "        return self.ans\n",
    "    \n",
    "    def backTrack(self, pre, preSum, target, start):\n",
    "        if preSum >= target:\n",
    "            if preSum > target:\n",
    "                return\n",
    "            self.ans.append(pre.copy())\n",
    "        else:\n",
    "            for j in range(start, len(self.nums)):\n",
    "                pre.append(self.nums[j])\n",
    "                preSum += self.nums[j]\n",
    "                self.backTrack(pre, preSum, target, j)\n",
    "                preSum -= self.nums[j]\n",
    "                pre.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "        # candidates.sort()\n",
    "        global ans \n",
    "        ans = []\n",
    "        \n",
    "        def find(index,list1,target,sum1):\n",
    "            if sum1 == target :\n",
    "                global ans\n",
    "                if sorted(list1) not in ans:\n",
    "                    ans.append(sorted(list1.copy()))\n",
    "                    # print(list1)\n",
    "                return\n",
    "            elif sum(list1)>target:\n",
    "                return\n",
    "            else:\n",
    "                for i in range(index,n):\n",
    "                    # list1+=[ candidates[i] ]\n",
    "                    find(i,list1+[ candidates[i] ],target,sum1+candidates[i])\n",
    "  \n",
    "                    \n",
    "\n",
    "        \n",
    "        find(0,[],target,0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(target,idx):\n",
    "            \n",
    "            if idx==len(candidates) or target<0:\n",
    "                return \n",
    "            if target==0:\n",
    "                ans.append(squence[:])\n",
    "                return \n",
    "            dfs(target,idx+1)\n",
    "            squence.append(candidates[idx])\n",
    "            dfs(target-candidates[idx],idx)\n",
    "            squence.pop()\n",
    "        squence=list()\n",
    "        ans=list()\n",
    "        candidates.sort()\n",
    "        dfs(target,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "\n",
    "        def dfs(index: int, rest: int):\n",
    "            if rest < 0:\n",
    "                return\n",
    "            if rest == 0:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                path.append(candidates[i])\n",
    "                dfs(i, rest - candidates[i])\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 暴力遍历所有的数种类情况\n",
    "        # 选择1，2，3... n 个数\n",
    "        # 回溯模板代码\n",
    "        final = []\n",
    "        def dfs(ind, result, target):\n",
    "            # 临界条件\n",
    "            if target == 0:\n",
    "                final.append(result.copy())\n",
    "                return\n",
    "            if ind >= len(candidates):\n",
    "                return\n",
    "            # 回溯递归, 选还是不选\n",
    "            \n",
    "            if candidates[ind] <= target:\n",
    "                result.append(candidates[ind])\n",
    "                dfs(ind, result, target-candidates[ind])\n",
    "                # 回溯\n",
    "                result.pop()\n",
    "            # else:\n",
    "                # dfs(ind+1, result, target)\n",
    "            dfs(ind+1, result, target)\n",
    "                \n",
    "        dfs(0, [], target)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "\n",
    "        def combi(candidates, target, start, end):\n",
    "            rs = []\n",
    "            for i in range(start, end):\n",
    "                num = candidates[i]\n",
    "                if target == num:\n",
    "                    # 当前num 和 target 相等, 则 [num] 作为一种组合\n",
    "                    rs.append([num])\n",
    "                elif target > num:\n",
    "                    # 当 target > num, 我们可以取 num, 然后继续向后取\n",
    "                    x = combi(candidates, target - num, i, end)\n",
    "                    if x:\n",
    "                        for com in x:\n",
    "                            com.append(num)\n",
    "                            rs.append(com)\n",
    "                else:\n",
    "                    # 当前 num > target, 后续也是大于 target\n",
    "                    break\n",
    "\n",
    "            return rs\n",
    "        \n",
    "        return combi(candidates, target, 0, n)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 暴力遍历所有的数种类情况\n",
    "        # 选择1，2，3... n 个数\n",
    "        # 回溯模板代码\n",
    "        final = []\n",
    "        def dfs(ind, result, target):\n",
    "            # 临界条件\n",
    "            if target == 0:\n",
    "                final.append(result.copy())\n",
    "                return\n",
    "            if ind >= len(candidates):\n",
    "                return\n",
    "            # 回溯递归, 选还是不选\n",
    "            dfs(ind+1, result, target)\n",
    "            if candidates[ind] <= target:\n",
    "                result.append(candidates[ind])\n",
    "                dfs(ind, result, target-candidates[ind])\n",
    "                # 回溯\n",
    "                result.pop()\n",
    "            # else:\n",
    "                \n",
    "        dfs(0, [], target)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 对candidates进行排序\n",
    "        candidates.sort()\n",
    "        path = []\n",
    "        res = []\n",
    "        def backwards(start, sum, candidates):\n",
    "            # sum == target,将path添加到res中\n",
    "            if sum == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            # 剪枝\n",
    "            for i in range(start, len(candidates)):\n",
    "                sum += candidates[i]\n",
    "                # 剪枝\n",
    "                # 判断sum是否大于target，因为candidates是从小到大的，\n",
    "                # 若sum大于target，则不遍历序号i之后的值；\n",
    "                # 若sum小于target，将candidates[i]添加到path中，然后进行回溯\n",
    "                if sum <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    backwards(i, sum, candidates)\n",
    "                    del path[-1]\n",
    "                    sum -= candidates[i]\n",
    "                else:\n",
    "                    return\n",
    "        backwards(0, 0, candidates)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "        # candidates.sort()\n",
    "        global ans \n",
    "        ans = []\n",
    "        \n",
    "        def find(index,list1,target,sum1):\n",
    "            if sum1 == target :\n",
    "                global ans\n",
    "                if sorted(list1) not in ans:\n",
    "                    ans.append(sorted(list1.copy()))\n",
    "                    # print(list1)\n",
    "                return\n",
    "            elif sum(list1)>target:\n",
    "                return\n",
    "            else:\n",
    "                for i in range(index,n):\n",
    "                    list2 =list1 + [ candidates[i] ]\n",
    "                    find(i,list2,target,sum1+candidates[i])\n",
    "        \n",
    "        find(0,[],target,0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "\n",
    "        def combi(candidates, target, start, end):\n",
    "            rs = []\n",
    "            for i in range(start, end):\n",
    "                num = candidates[i]\n",
    "                if target == num:\n",
    "                    # 当前num 和 target 相等, 则 [num] 作为一种组合\n",
    "                    rs.append([num])\n",
    "                elif target > num:\n",
    "                    # 当 target > num, 我们可以取 num, 然后继续向后取, 不要从0开始取\n",
    "                    x = combi(candidates, target - num, i, end)\n",
    "                    if x:\n",
    "                        for com in x:\n",
    "                            com.append(num)\n",
    "                            rs.append(com)\n",
    "                else:\n",
    "                    # 当前 num > target, 后续也是大于 target\n",
    "                    break\n",
    "\n",
    "            return rs\n",
    "        \n",
    "        return combi(candidates, target, 0, n)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res =[]\n",
    "        self.path = []\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def back(candidates,start, target):\n",
    "            if target < 0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                print(self.path)\n",
    "                self.res.append(self.path[:])\n",
    "                return\n",
    "            for i in range(start, len(candidates)):\n",
    "                self.path.append(candidates[i])\n",
    "                back(candidates, i,target - candidates[i])\n",
    "                self.path.pop()\n",
    "        back(candidates, 0, target)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(candidates: List[int], target: int, idx: int, path: List[int]):\n",
    "            nonlocal res\n",
    "            if sum(path) == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            if sum(path) > target or idx > len(candidates) - 1:\n",
    "                return\n",
    "            for i in range(idx, len(candidates)):\n",
    "                if sum(path) + candidates[i] <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    dfs(candidates, target, i, path)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs(candidates, target, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        if not candidates:\n",
    "            return []\n",
    "        output = []\n",
    "        sorted(candidates)\n",
    "        def backtrace(begin:int,target:int,nums:list):\n",
    "            if target<0:\n",
    "                return \n",
    "            if target==0:\n",
    "                output.append(nums[:])\n",
    "            for i in range(begin,len(candidates)):\n",
    "                nums.append(candidates[i])\n",
    "                backtrace(i,target-candidates[i],nums)\n",
    "                nums.pop()\n",
    "        backtrace(0,target,[])\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def f(i,c,tmp):\n",
    "            if c>target:\n",
    "                return\n",
    "            if c==target:\n",
    "                ans.append(tmp[::])\n",
    "            for j in range(i,len(candidates)):\n",
    "                c+=candidates[j]\n",
    "                tmp.append(candidates[j])\n",
    "                f(j,c,tmp)\n",
    "                c-=candidates[j]\n",
    "                tmp.pop()\n",
    "        ans=[]\n",
    "        f(0,0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(step:int, ans: List[int], SUM: int)-> None:\n",
    "            if step==len(candidates):return\n",
    "            count = 0\n",
    "            while SUM<= target:\n",
    "                ans.append(candidates[step])\n",
    "                SUM+=candidates[step]\n",
    "                if SUM == target:res.append(ans.copy())\n",
    "                if SUM < target:dfs(step+1, ans, SUM)\n",
    "                count+=1\n",
    "            for i in range(count):\n",
    "                ans.pop()\n",
    "                SUM-=candidates[step]\n",
    "            dfs(step+1, ans, SUM)\n",
    "        dfs(0, [], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(candidates,begin, size, path ,res, target):\n",
    "            if target < 0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for index in range(begin, size):\n",
    "                # if candidates[index] not in path:\n",
    "                dfs(candidates, index, size, path + [candidates[index]], res, target- candidates[index])\n",
    "        \n",
    "        size = len(candidates)\n",
    "        path = []\n",
    "        res = []\n",
    "        dfs(candidates, 0, size, path, res, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(candidates)\n",
    "        if n == 0:\n",
    "            return ans\n",
    "        path = []\n",
    "        def helper(index, total):\n",
    "            if total > target:\n",
    "                return\n",
    "            if total == target:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                path.append(candidates[i])\n",
    "                helper(i, total + candidates[i])\n",
    "                path.pop()\n",
    "        helper(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(nums, start, target, path):\n",
    "            if target == 0:\n",
    "                 ans.append(path.copy())\n",
    "            if target < 0:\n",
    "                return \n",
    "            if start >= len(nums):\n",
    "                return \n",
    "            for i in range(start, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                dfs(nums, i, target - nums[i], path)\n",
    "                path.pop()\n",
    "        ans = []\n",
    "        dfs(candidates, 0, target, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Backtrack. Time O(S) Space O(target)\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(combine, target, idx):\n",
    "            if target < 0: return\n",
    "            if target == 0:\n",
    "                res.append(combine[:])\n",
    "                return\n",
    "            for i in range(idx, len(candidates)):\n",
    "                combine.append(candidates[i])\n",
    "                # set idx to i as i can be chosen again\n",
    "                dfs(combine, target - candidates[i], i)\n",
    "                combine.pop()\n",
    "        dfs([], target, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        ans = []\n",
    "        def backup(cur, tmp, index):\n",
    "            if cur == 0:\n",
    "                ans.append(tmp[:])\n",
    "                return\n",
    "            for i in range(index, len(candidates)):\n",
    "                if cur - candidates[i] >= 0:\n",
    "                    cur -= candidates[i]\n",
    "                    tmp.append(candidates[i])\n",
    "                    backup(cur, tmp, i)\n",
    "                    cur += candidates[i]\n",
    "                    tmp.pop()\n",
    "            return\n",
    "        backup(target, [], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # candidates.sort(reverse=True)\n",
    "        ans = []\n",
    "        tmp = []\n",
    "        Len = len(candidates)\n",
    "        candidates.sort()\n",
    "        def f(i, left):\n",
    "            nonlocal tmp\n",
    "            \n",
    "            if i == Len:\n",
    "                return\n",
    "            n = left // candidates[i]\n",
    "            if n == 0:\n",
    "                return \n",
    "            for k in range(0, n+1):\n",
    "                if candidates[i] * k == left:\n",
    "                    tmp_bk = tmp.copy()\n",
    "                    tmp.extend([candidates[i]] * k)\n",
    "                    ans.append(tmp)\n",
    "                    tmp = tmp_bk\n",
    "                else :\n",
    "                    tmp_bk = tmp.copy()\n",
    "                    tmp.extend([candidates[i]] * k)\n",
    "                    f(i+1, left-candidates[i] * k)\n",
    "                    tmp = tmp_bk\n",
    "\n",
    "        f(0, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "\n",
    "        def dfs(start,path,cursum):\n",
    "            if cursum == target:\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            for i in range(start,n):\n",
    "                if cursum+candidates[i] <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    dfs(i,path,cursum+candidates[i])\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    return\n",
    "        dfs(0,path,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res, comb = [], []\n",
    "\n",
    "        candidates.sort()\n",
    "        \n",
    "        def dfs(target, idx):\n",
    "            if target == 0 and len(comb) > 0: \n",
    "                res.append(comb.copy())\n",
    "                return\n",
    "            if idx == len(candidates) or target < candidates[idx]: \n",
    "                return\n",
    "            dfs(target, idx + 1)\n",
    "            \n",
    "            target_left = target - candidates[idx]\n",
    "            if target_left >= 0:\n",
    "                comb.append(candidates[idx])\n",
    "                dfs(target_left, idx)\n",
    "                comb.pop()\n",
    "        dfs(target, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ret = []\n",
    "        n = len(candidates)\n",
    "        def dfs(pos,cur,sums):\n",
    "            # print(cur)\n",
    "            if sums == target:\n",
    "                ret.append(cur[:])\n",
    "                return \n",
    "            if sums > target or pos >= n:\n",
    "                return\n",
    "            dfs(pos,cur + [candidates[pos]],sums + candidates[pos])\n",
    "            dfs(pos+1,cur,sums)\n",
    "        dfs(0,[],0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "    res = []\n",
    "    path = []\n",
    "    n = len(candidates)\n",
    "    candidates.sort()\n",
    "\n",
    "    def dfs(index, sum):\n",
    "      if sum >= target:\n",
    "        if sum == target:\n",
    "          res.append(path.copy())\n",
    "          return\n",
    "      \n",
    "      for i in range(index, n):\n",
    "        if sum + candidates[i] > target: return\n",
    "        path.append(candidates[i])\n",
    "        dfs(i, sum + candidates[i])\n",
    "        path.pop()\n",
    "\n",
    "    dfs(0, 0)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, cand: List[int], target: int) -> List[List[int]]:\n",
    "        #cand.sort()\n",
    "        #无剪枝版本\n",
    "        ans=[]\n",
    "        n=len(cand)\n",
    "        def find(target,idx,path):\n",
    "            if target<0 or idx>=n:\n",
    "                return\n",
    "            if target==0:\n",
    "                ans.append(path[:])\n",
    "                #path[:]相当于是一次深拷贝\n",
    "            for i in range(idx,n):#可重复收集\n",
    "                path.append(cand[i])\n",
    "                find(target-cand[i],i,path)\n",
    "                path.pop()\n",
    "        find(target,0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(idx, t):\n",
    "            nonlocal n\n",
    "            if idx >= n or t > target:\n",
    "                return\n",
    "            if t == target:\n",
    "                res.add(tuple(tmp))\n",
    "                return\n",
    "            dfs(idx + 1, t)\n",
    "            t += candidates[idx]\n",
    "            tmp.append(candidates[idx])\n",
    "            dfs(idx, t)\n",
    "            dfs(idx + 1, t)\n",
    "            tmp.pop()\n",
    "        \n",
    "        tmp = []\n",
    "        res = set()\n",
    "        n = len(candidates)\n",
    "        dfs(0, 0)\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        results = []\n",
    "\n",
    "        def dfs(paths, index):\n",
    "            if sum(paths) == target:\n",
    "                results.append(paths)\n",
    "                return\n",
    "            \n",
    "            if sum(paths)>target:\n",
    "                return\n",
    "\n",
    "            for i in range(index, len(candidates)):\n",
    "                dfs(paths + [candidates[i]], i)\n",
    "\n",
    "        dfs([], 0)\n",
    "        print(results)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        ans = []\n",
    "        path = []\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        def dfs(i, count):\n",
    "            if count < 0:\n",
    "                return \n",
    "            if count  == 0:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "\n",
    "            for j in range(i, n):\n",
    "                c= candidates[j]\n",
    "                if c > target:\n",
    "                    break\n",
    "                \n",
    "                path.append(c)\n",
    "                dfs(j, count - c)\n",
    "                path.pop()\n",
    "            \n",
    "        dfs(0, target)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
